/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-23 17:45:24
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-23 18:09:42
 * @FilePath: \LeetCode\118.杨辉三角.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=118 lang=cpp
 *
 * [118] 杨辉三角
 *
 * 方法1：动态规划
 * - dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
 */

#include <vector>

// @lc code=start
class Solution
{
public:
    std::vector<std::vector<int>> generate(int numRows)
    {
        std::vector<std::vector<int>> YH_triangle;
        YH_triangle.resize(numRows);
        YH_triangle[0] = {1};

        for (int i = 1; i < numRows; i++)
        {
            YH_triangle[i] = std::vector<int>(i + 1, 1);
            /* dp[i][j] = dp[i-1][j-1] + dp[i-1][j] */
            for (int j = 1; j < i; j++)
                YH_triangle[i][j] = YH_triangle[i - 1][j - 1] + YH_triangle[i - 1][j];
        }

        return YH_triangle;
    }
};
// @lc code=end
